package 代码记录.剑指offer错题本;

/**
 * @author zx
 * @create 2022-06-09 20:11
 */
public class 数组中数字出现的次数_56 {
    /**
     * 异或：相同取0,相异取1,(0异或任何数都为本身)
     * @return
     * 先对所有数字进行一次异或,得到两个出现一次的数字的异或值
     * 在异或结果中找到任意为 1 的位
     * 根据这一位对所有的数字进行分组
     * 在每个组内进行异或操作,得到两个数字
     */
    public int[] singleNumbers(int[] nums) {
        int res = 0;
        for(int n : nums) {
            res ^= n;//设两个只出现一次的数分别为a和b,获得a异或b的结果
        }
        //找到ab第一个不相同的二进制位(temp),用位与&操作
        //通过1的位置变化找出首个不一样的二进制位
        int temp = 1;
        while((temp & res) == 0) {//eg：temp=000001,当第一位不是1时,结果为0,则temp左移一位,000010类推直到找出
            temp <<= 1;
        }
        //找到temp后,用temp划分数组,两个相同的数字,在temp位一定相同,其与temp位与的结果一定相同,按temp&n==0划分,就定能保证：
        //(1) 原来相同的元素还在一组
        //(2) 不同的两个元素被分到了不同组
        int a = 0, b = 0;
        for(int n : nums) {
            if((n & temp) == 0) {
                a ^= n;
            }else {
                b ^= n;
            }
        }
        return new int[]{a, b};
    }
}
